package com.ycy.leetcode.tree;

import com.google.common.collect.Lists;
import org.junit.Before;
import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * 前序 中序 后序
 * 树的最大深度
 * 层序遍历
 */
public class TreeBianLi1 {

  TreeNode root;

  @Before
  public void before() {

    /*
         500
    250      1000
  150 350  750 1250
           /
         650
     */
    root = new TreeNode(500);
    root.l = new TreeNode(250);
    root.r = new TreeNode(1000);

    root.l.l = new TreeNode(150);
    root.l.r = new TreeNode(350);

    root.r.l = new TreeNode(750);
    root.r.r = new TreeNode(1250);

    root.r.l.l = new TreeNode(650);

  }

  /**
   * 求树的最大深度
   */
  public void depth() {

  }

  @Test
  public void test1() {
    print(this.root);
  }

  /**
   * 前序遍历
   */
  public void print(TreeNode root) {
    if (root == null) return;
    System.out.println(root.value);
    print(root.l);
    print(root.r);
  }

  @Test
  public void validBST() {
    System.out.println(validBST(root));
  }

  int pre = Integer.MIN_VALUE;

  public boolean validBST(TreeNode root) {
    if (root == null) {
      return true;
    }
    if (!validBST(root.l)) {
      return false;
    }
    if (root.value < pre) {
      return false;
    }
    pre = root.value;
    return validBST(root.r);
  }

  @Test
  public void test4() {
    rang(root);
  }

  int min = 250;
  int max = 1000;

  /**
   * 范围查询
   */
  public boolean rang(TreeNode root) {
    if (root == null) {
      return true;
    }
    if (!rang(root.l)) {
      return false;
    }
    if (min <= root.value && root.value <= max) {
      System.out.println(root.value);
    }
    if (root.value > max) return false;
    return rang(root.r);
  }

  @Test
  public void test5() {

    List<Integer> list = Lists.newArrayList();
    target = 650;
    lujing(root, list);
    for (Integer integer : list) {
      System.out.println(integer);
    }

  }

  int target = 0;

  /**
   * 查询路径
   */
  public boolean lujing(TreeNode node, List<Integer> list) {

    if (node == null) {
      return false;
    }

    list.add(node.value);
    if (node.value == target) {
      return true;
    }
    boolean lujing = lujing(node.l, list);
    if (lujing) {
      return lujing;
    }
    boolean lujing1 = lujing(node.r, list);
    if (lujing1) {
      return lujing1;
    }
    list.remove(list.size() - 1);
    return false;
  }

  @Test
  public void test6() {
    List<TreeNode> path = getPath(root, new TreeNode(650));
    for (TreeNode treeNode : path) {
      System.out.println(treeNode.value);
    }
  }

  public List<TreeNode> getPath(TreeNode root, TreeNode target) {

    List<TreeNode> path = new ArrayList<TreeNode>();
    TreeNode cur = root;
    while (cur != null) {
      path.add(cur);
      if (cur.value < target.value) {
        cur = cur.r;
      } else if (cur.value > target.value) {
        cur = cur.l;
      } else {
        break;
      }
    }
    return path;
  }

  class TreeNode {
    TreeNode l;
    TreeNode r;
    int value;

    public TreeNode(int vlaue) {
      this.value = vlaue;
    }
  }

}
